package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
 *
 *
 * 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
 * 输出：3
 * 解释：长度最长的公共子数组是 [3,2,1] 。
 * 示例 2：
 *
 * 输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
 * 输出：5
 *
 *
 * @author hanjuntao
 * @date 2025/6/7 0007
 */
public class UL_718_maximum_length_of_repeated_subarray {

    public static void main(String[] args) {
        //System.out.println(findLength(new int[]{1,2,3,2,1}, new int[]{3,2,1,4,7}));

        System.out.println(findLength(new int[]{0,0,0,0,0,0,1,0,0,0}, new int[]{0,0,0,0,0,0,0,1,0,0}));
    }

    /**
     * 暴力解法
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static int findLength(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return 0;
        }

        int len1 = nums1.length;
        int len2 = nums2.length;

        int[] longArr;
        int[] shortArr;
        if (len1 > len2) {
            longArr = nums1;
            shortArr = nums2;
        } else {
            longArr = nums2;
            shortArr = nums1;
        }

        int maxLen = 0;

        // 控制短数组移动
        for (int i = 0; i < shortArr.length; i++) {
            // 如果最大的长度>= 数组剩余的长度，就不需要再检测了
            if (maxLen >= shortArr.length - i) {
                break;
            }

            // 比对长数组
            maxLen = getMaxLen(longArr, i, shortArr, maxLen);
        }

        return maxLen;
    }

    private static int getMaxLen(int[] longArr, int i, int[] shortArr, int maxLen) {
        int oldI = i;
        // 找到第一个比对成功的，这个比对完后，继续监测
        for (int x = 0; x < longArr.length; x++) {
            // 如果最大的长度>= 数组剩余的长度，就不需要再检测了
            if (maxLen >= longArr.length - x) {
                break;
            }

            // 检测短的数组，有没有重复的
            Integer beginIndex = null;
            Integer endIndex = null;

            for (int j = x; j < longArr.length; j++) {
                if (i >= shortArr.length) {
                    break;
                }
                // 如果有相等的，那么持续后移
                // 短数据也一起推移
                if (shortArr[i] == longArr[j]) {
                    if (beginIndex == null) {
                        beginIndex = j;
                        endIndex = beginIndex;
                    } else {
                        endIndex++;
                    }
                    i++;
                } else {
                    if (beginIndex != null) {
                        break;
                    }
                }
            }

            if (beginIndex != null && endIndex != null) {
                int size = endIndex - beginIndex + 1;

                if (size > maxLen) {
                    maxLen = size;
                }
            }

            i = oldI;
        }

        return maxLen;

    }


    /**
     * 滑动窗口
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static int findLength2(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int maxLen = 0;
        int totalMax = Math.min(len1, len2); // 全局可能的最大长度

        // 枚举所有可能的偏移量（从 -len2+1 到 len1-1）
        for (int offset = -len2 + 1; offset < len1; offset++) {
            // 如果已经找到全局最大值，提前结束
            if (maxLen == totalMax) {
                break;
            }

            // 计算当前偏移下的重叠区域
            int aStart = Math.max(offset, 0);
            int bStart = Math.max(-offset, 0);
            int overlap = Math.min(len1 - aStart, len2 - bStart);

            // 如果剩余重叠区域长度小于当前最大值，跳过
            if (overlap <= maxLen) {
                continue;
            }

            int currentLen = 0;
            for (int i = 0; i < overlap; i++) {
                if (nums1[aStart + i] == nums2[bStart + i]) {
                    currentLen++;
                    maxLen = Math.max(maxLen, currentLen);
                    // 提前结束条件
                    if (maxLen == totalMax) {
                        break;
                    }
                } else {
                    currentLen = 0; // 重置连续计数
                }
            }
        }
        return maxLen;
    }

}
